package com.foxzzz.temporary;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution322 {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0)
            return 0;
        Map<Integer, Integer> map = new HashMap<>();
        int result = coin(coins, amount, map);
        return result == Integer.MAX_VALUE ? -1 : result;

    }

    public int coin(int[] coin, int amount, Map<Integer, Integer> minMap) {
        if (minMap.containsKey(amount))
            return minMap.get(amount);
        int min = Integer.MAX_VALUE;
        for (int i : coin) {
            int am = amount - i;
            int val = 0;
            if (am < 0)
                val = Integer.MAX_VALUE;
            else if (am == 0)
                val = 1;
            else {
                int result = coin(coin, am, minMap);
                val = result == Integer.MAX_VALUE ? result : result + 1;
            }
            min = min < val ? min : val;
        }
        minMap.put(amount, min);
        return min;
    }


    public static void main(String[] args) {
       // System.out.println(new Solution322().coinChange(new int[]{9}, 100));
    }
}

